package arithmetic_40;

import java.util.ArrayList;
import java.util.List;

/**
 *
 * @author wxh
 */
public class Solution_5 {

	public List<String> generateParenthesis(int n) {

		List<String> list = new ArrayList<>();
		//
		gen(0 , 0, n, list, "");
		return list;

	}

	/**
	 * @param left 左括已用数量
	 * @param right 右括号已用数量
	 * @param n 总共多个对括号
	 * @param list 合法的条件的结果集
	 * @param result 当前产生括号的string
	 */
	public void gen(int left, int right, int n, List<String> list, String result) {

		// 左右括号资源资源都用完，说明result组装完毕，直接加到数组
		if (left == n && right == n) {
			list.add(result);
			return;
		}

		// 如果左括号没用完，则左括号多用一个（左括号只要没用完，随时都可以加进去）
		if (left < n) {
			gen(left + 1, right, n, list, result + "(");
		}

		// 右括号没有用完，且右括号的总数要比左括号少（否则直接加右括号则不合法），则右括号多用一个
		if (right < n && right < left) {
			gen(left, right + 1, n ,list, result + ")");
		}

	}

	public static void main(String[] args) {
		Solution_5 solution_5 = new Solution_5();
		System.out.println(solution_5.generateParenthesis(3));
	}

}